class Solution:
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        给定一个没有重复数字的序列，返回其所有可能的全排列。
        个数为n!
        """
        if len(nums) < 2:
            return [nums]
        i = 0
        res = []
        while i < len(nums):
            # print(111)
            # print(nums)
            tmp, tmp2, j = [], [], 0
            nums2 = nums[:]
            nums2.pop(i)
            while j < len(nums2):
                tmp = nums2[j:len(nums2)]
                tmp.extend(nums2[0:j])
                tmp.insert(0, nums[i])
                res.append(tmp)
                j += 1
            i += 1

        return res

    def permute2(self, nums):
        res = []
        self.dfs(nums, [], res)
        return res

    # 递归算法
    def dfs(self, nums, path, res):
        # print("nums");print(nums);
        # print("path");print(path);
        if not nums:
            res.append(path)
            # return # backtracking
        for i in range(len(nums)):
            self.dfs(nums[:i] + nums[i + 1:], path + [nums[i]], res)


sol = Solution()
nums = [1, 2, 3, 4]
nums1 = [1, 2, 3]
nums2 = [1, 2]
nums3 = [1]
res = sol.permute2(nums1)
print(res)

